#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }
};
class Solution
{
  public:
    TreeNode *dfs(TreeNode *root, int p, int q)
    {
        if (root == nullptr)
            return nullptr;
        if (root->val == p || root->val == q)
            return root;
        TreeNode *left = dfs(root->left, p, q);
        TreeNode *right = dfs(root->right, p, q);
        if (left != nullptr && right != nullptr)
            return root;
        if (left == nullptr && right != nullptr)
            return right;
        if (left != nullptr && right == nullptr)
            return left;
        else
            return nullptr;
    }
    int lowestCommonAncestor(TreeNode *root, int o1, int o2)
    {
        // write code here
        TreeNode *ans = dfs(root, o1, o2);
        return ans->val;
    }
};